1.1 Field of the Invention
The present invention relates to methods and apparatus for controlling the gain of signals before sampling and quantization. The invention further relates to methods that use randomized measurement systems, democratic measurement systems, and compressive measurement systems. The invention is applicable to any type of signal or sampling and quantization system, however, its inherent properties will only be beneficial to some.
1.2 Brief Description of the Related Art
1.2.1 Analog-to-digital Conversion
Analog-to-digital conversion (ADC) consists of two discretization steps: sampling, which converts a continuous-time signal to a discrete-time set of measurements, followed by quantization, which converts the continuous value of each measurement to a discrete one chosen from a pre-determined, finite set. Both steps are necessary to represent an analog signal in the discrete digital world.
The discretization step can be lossless or lossy. For example, classical results due to Shannon and Nyquist demonstrate that the sampling step induces no loss of information, provided that the signal is bandlimited and a sufficient number of measurements (or samples) are obtained. Similarly, sensing of images assumes that the image is sufficiently smooth such that the integration of light in each pixel of the sensor is sufficient for a good quality representation of the image. The present invention relies the existence of a discretization that exactly represents the signal, or approximates the signal to sufficient quality. Examples of such discretizations and their implementation in the context of compressive sensing can be found in J. Tropp, J. Laska, M. Duarte, J. Romberg, and R. Baraniuk, “Beyond Nyquist: Efficient sampling of sparse, bandlimited signals,” to appear in IEEE Trans. Inform. Theory, 2009, J. Romberg, “Compressive sensing by random convolution,” to appear in SIAM J. Imaging Sciences, 2009, J. Tropp, M. Wakin, M. Duarte, D. Baron, and R. Baraniuk, “Random filters for compressive sampling and reconstruction,” in Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing (ICASSP), Toulouse, France, May 2006, M. Duarte, M. Davenport, D. Takhar, J. Laska, T. Sun, K. Kelly, and R. Baraniuk, “Single-pixel imaging via compressive sampling,” IEEE Signal Processing Mag., vol. 25, no. 2, pp. 83-91, 2008, R. Robucci, L. Chiu, J. Gray, J. Romberg,
TABLE 1Quantization parameters.Gsaturation levelBnumber of bitsΔbin widthΔ/2maximum error per (quantized) measurementunboundedmaximum error per (saturated) measurementP. Hasler, and D. Anderson, “Compressive sensing on a CMOS separable transform image sensor,” in Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing (ICASSP), Las Vegas, Nev., April 2008, R. Marcia, Z. Harmany, and R. Willett, “Compressive coded aperture imaging,” in Proc. SPIE Symp. Elec. Imaging: Comput. Imaging, San Jose, Calif., January 2009, Y. Eldar and M. Mishali, “Robust recovery of signals from a structured union of subspaces,” to appear in IEEE Trans. Inform. Theory, 2009, M. Mishali, Y. Eldar, and J. Tropp, “Efficient sampling of sparse wideband analog signals,” in Proc. Conv. IEEE in Israel (IEEEI), Eilat, Israel, December 2008, M. Mishali and Y. Eldar, “From theory to practice: Sub-Nyquist sampling of sparse wideband analog signals,” Preprint, 2009, Y. Eldar and M. Mishali, “Robust recovery of signals from a structured union of subspaces,” to appear in IEEE Trans. Inform. Theory, 2009. Certain aspects of such systems are discussed briefly below in Sec. 1.2.4.
Instead, the present discussion is focused on the second aspect of digitization, namely quantization. Quantization results in an irreversible loss of information unless the measurement amplitudes belong to the discrete set defined by the quantizer. A central ADC system design goal is to minimize the distortion due to quantization.
1.2.2 Scalar Quantization
Scalar quantization is the process of converting the continuous value of an individual measurement to one of several discrete values through a non-invertible function R(•). Practical quantizers introduce two kinds of distortion: bounded quantization error and unbounded saturation error.
In a preferred embodiment of our invention, we focus on uniform quantizers with quantization interval Δ. Thus, the quantized values become qk=q0+kΔ, for kε, and every measurement g is quantized to the nearest quantization level R(g)=argminqk|g−qk|=Δ/2+kΔ, the midpoint of each quantization interval. This minimizes the expected quantization distortion and implies that the quantization error per measurement, |g−R(q)|, is bounded by Δ/2. FIG. 1A depicts the mapping performed by a midrise quantizer.
In practice, quantizers have a finite dynamic range, dictated by hardware constraints such as the voltage limits of the devices and the finite number of bits per measurement of the quantized representation. Thus, a finite-range quantizer represents a symmetric range of values |g|<G, where G>0 is known as the saturation level G. Gray and G. Zeoli, “Quantization and saturation noise due to analog-to-digital conversion,” IEEE Trans. Aerospace and Elec. Systems, vol. 7, no. 1, pp. 222-223, 1971. Values of g between −G and G will not saturate, thus, the quantization interval is defined by these parameters as Δ=2−B+1G. Without loss of generality we assume a midrise B-bit quantizer, i.e., the quantization levels are qk=Δ/2+kΔ, where k=−2B−1, . . . , 2B−1−1. Any measurement with magnitude greater than G saturates the quantizer, i.e., it quantizes to the quantization level G−Δ/2, implying an unbounded error. FIG. 1B depicts the mapping performed by a finite range midrise quantizer with saturation level G and Table 1 summarizes the parameters defined with respect to quantization.
1.2.3 Compressive Sensing (CS)
In the CS framework, we acquire a signal xεN via the linear measurementsy=Φx+e,  (1)where Φ is an M×N measurement matrix modeling the sampling system, yεM is the vector of samples acquired, and e is an M×1 vector that represents measurement errors. If x is K-sparse when represented in the sparsity basis Ψ, i.e., x=Ψα with ∥α∥0:=|supp(α)|≦K, then one can acquire just M=O(K log(N/K)) measurements and still recover the signal x. A similar guarantee can be obtained for approximately sparse, or compressible, signals. Observe that if K is small, then the number of measurements required can be significantly smaller than the Shannon-Nyquist rate.
In E. Candès and T. Tao, “Decoding by linear programming,” IEEE Trans. Inform. Theory, vol. 51, no. 12, pp. 4203-4215, 2005, Candès and Tao introduced the restricted isometry property (RIP) of a matrix Φ and established its important role in CS. From E. Candès and T. Tao, “Decoding by linear programming,” IEEE Trans. Inform. Theory, vol. 51, no. 12, pp. 4203-4215, 2005, we have the definition,
Definition 1. A matrix Φ satisfies the RIP of order K with constant δε(0, 1) if(1−δ)∥x∥22≦∥Φx∥22≦(1+δ)∥x∥22  (2)holds for all x such that ∥x∥0≦K.
In words, Φ acts as an approximate isometry on the set of vectors that are K-sparse in the basis Ψ. An important result is that for any unitary matrix Ψ, if we draw a random matrix Φ whose entries φij are independent realizations from a sub-Gaussian distribution, then ΦΨ will satisfy the RIP of order K with high probability provided that M=O(K log(N/K)) R. Baraniuk, M. Davenport, R. DeVore, and M. Wakin, “A simple proof of the restricted isometry property for random matrices,” Const. Approx., vol. 28, no. 3, pp. 253-263, 2008. Without loss of generality, we fix Ψ=I, the identity matrix, implying that x=α.
The RIP is a necessary condition if we wish to be able to recover all sparse signals x from the measurements y. Specifically, if ∥x∥0=K, then Φ must satisfy the lower bound of the RIP of order 2K with δ<1 in order to ensure that any algorithm can recover x from the measurements y. Furthermore, the RIP also suffices to ensure that a variety of practical algorithms can successfully recover any sparse or compressible signal from noisy measurements. In particular, for bounded errors of the form ∥e∥2≦ε, the convex program
                              x          ^                =                                            argmin              x                        ⁢                                                          x                                            1                        ⁢                                                  ⁢                          s              .              t              .                                                          ⁢                                                                                                            Φ                      ⁢                                                                                          ⁢                      x                                        -                    y                                                                    2                                              ≤          ε                                    (        3        )            can recover a sparse or compressible signal x. The following theorem, a slight modification of Theorem 1.2 from E. Candès, “The restricted isometry property and its implications for compressed sensing,” Comptes rendus de l'Académie des Sciences, Série I, vol. 346, no. 9-10, pp. 589-592, 2008, makes this precise by bounding the recovery error of x with respect to the measurement noise norm, denoted by ε, and with respect the best approximation of x by its largest K terms, denoted using xK.Theorem 1. Suppose that ΦΨ satisfies the RIP of order 2K with δ<√{square root over (2)}−1. Given measurements of the form y=ΦΨx+e, where ∥e∥2≦ε, then the solution to (3) obeys
                                                                  x              ^                        -            x                                    2            ≤                                    C            0                    ⁢          ε                +                              C            1                    ⁢                                                                                      x                  -                                      x                    K                                                                              1                                      K                                            ,                  ⁢    where                      C        0            =                        4          ⁢                      (                          1              +              δ                        )                                    1          -                                    (                                                2                                +                1                            )                        ⁢            δ                                ,                  C        1            =                                    1            +                                          (                                                      2                                    -                  1                                )                            ⁢              δ                                            1            -                                          (                                                      2                                    +                  1                                )                            ⁢              δ                                      .            
While convex optimization techniques like equation (3) are a powerful method for CS signal recovery, there also exist a variety of alternative algorithms that are commonly used in practice and for which performance guarantees comparable to that of Theorem 1 can be established. In particular, iterative algorithms such as CoSaMP and iterative hard thresholding (IHT) are known to satisfy similar guarantees under slightly stronger assumptions on the RIP constants. Furthermore, alternative recovery strategies based on (3) have been analyzed in E. Candès and T. Tao, “The Dantzig selector: Statistical estimation when p is much larger than n,” Annals of Statistics, vol. 35, no. 6, pp. 2313-2351, 2007, P. Wojtaszczyk, “Stability and instance optimality for Gaussian measurements in compressed sensing,” to appear in Found. Comput. Math., 2009. These methods replace the constraint in (3) with an alternative constraint that is motivated by the assumption that the measurement noise is Gaussian in the case of E. Candès and T. Tao, “The Dantzig selector: Statistical estimation when p is much larger than n,” Annals of Statistics, vol. 35, no. 6, pp. 2313-2351, 2007 and that is agnostic to the value of ε in P. Wojtaszczyk, “Stability and instance optimality for Gaussian measurements in compressed sensing,” to appear in Found. Comput. Math., 2009.
1.2.4 CS in Practice
Several hardware architectures have been proposed and implemented that allow CS to be used in practical settings with analog signals. Examples include the random demodulator, random filtering, and random convolution for signals. J. Tropp, J. Laska, M. Duarte, J. Romberg, and R. Baraniuk, “Beyond Nyquist: Efficient sampling of sparse, bandlimited signals,” to appear in IEEE Trans. Inform. Theory, 2009, as well as the modulated wideband converter for multiband signals, and several compressive imaging architectures M. Duarte, M. Davenport, D. Takhar, J. Laska, T. Sun, K. Kelly, and R. Baraniuk, “Single-pixel imaging via compressive sampling,” IEEE Signal Processing Mag., vol. 25, no. 2, pp. 83-91, 2008, R. Robucci, L. Chiu, J. Gray, J. Romberg, P. Hasler, and D. Anderson, “Compressive sensing on a CMOS separable transform image sensor,” in Proc. IEEE Int. Conf. Acoustics, Speech, and Signal Processing (ICASSP), Las Vegas, Nev., April 2008, R. Marcia, Z. Harmany, and R. Willett, “Compressive coded aperture imaging,” in Proc. SPIE Symp. Elec. Imaging: Comput. Imaging, San Jose, Calif., January 2009.
A random demodulator is briefly described as an example of such a system in J. Tropp, J. Laska, M. Duarte, J. Romberg, and R. Baraniuk, “Beyond Nyquist: Efficient sampling of sparse, bandlimited signals,” to appear in IEEE Trans. Inform. Theory, 2009. FIG. 2 depicts the block diagram of the random demodulator. The four key components are a pseudo-random ±1 “chipping sequence” pc(t) operating at the Nyquist rate or higher, a low pass filter, often represented by an ideal integrator with reset, a low-rate ADC, and a quantizer. An input analog signal x(t) is modulated by the chipping sequence and integrated. The output of the integrator is sampled, and the integrator is reset after each sample. The output measurements from the ADC are then quantized.
Systems such as these represent a linear operator mapping the analog input signal to a discrete output vector, followed by a quantizer. It is possible, but beyond the scope of this description, to relate this operator to a discrete measurement matrix Φ which maps, for example, the Nyquist-rate samples of the input signal to the discrete output vector J. Tropp, J. Laska, M. Duarte, J. Romberg, and R. Baraniuk, “Beyond Nyquist: Efficient sampling of sparse, bandlimited signals,” to appear in IEEE Trans. Inform. Theory, 2009, M. Mishali and Y. Eldar, “From theory to practice: Sub-Nyquist sampling of sparse wideband analog signals,” Preprint, 2009, J. Treichler, M. Davenport, and R. Baraniuk, “Application of compressive sensing to the design of wideband signal acquisition receivers,” in U.S./Australia Joint Work. Defense Apps. of Signal Processing (DASP), Lihue, Hi., September 2009. In this application the description is focused on settings in which the measurement operator Φ can be represented as an M×N matrix.
1.2.5 Saturation and Compressive Sensing
It has been shown that CS systems can be made robust to saturated measurements. One approach simply discards saturated measurements and performs signal reconstruction without them. Another approach is based on an alternative CS recovery algorithm that treats saturated measurements differently from unsaturated ones. This is achieved by employing a magnitude constraint on the indices of the saturated measurements while maintaining the conventional regularization constraint on the indices of the other measurements.
These methods exploit the democratic nature of CS measurements. Because each measurement contributes equally to the compressed representation, some of them can be removed while still maintaining a sufficient amount of information about the signal to enable recovery.
When employing these methods, in order to maximize the acquisition SNR, the optimal strategy is to allow the quantizer to saturate at some nonzero rate. This is due to the inverse relationship between quantization error and saturation rate: as the saturation rate increases, the distortion of remaining measurements decreases. Furthermore, experimental results show that on average, the optimal SNR is achieved at nonzero saturation rates.